The invention relates to a method of transforming a bit-reversed order vector stored in a main memory unit (MMU) of a vector processing system into a natural order vector.
FIG. 5 is a diagram for explaining how a calculation of the fast Fourier transform (FFT) is done by the use of a vector processing system according to the method disclosed in a paper entitled "An Adaptation of the Fast Fourier Transform for Parallel Processing" by Marshall C. Pease, published in the Journal of the Association for Computing Machinery, Vol. 15, No. 2, April issue, 1968, pp. 252-264. It is supposed that an input vector consisting of eight vector elements X(0), X(1), X(2), X(3), X(4), X(5), X(6) and X(7) of eight bits each is stored in a MMU of a vector processing system. These elements X(0) to X(7) are stored in eight consecutive storage locations of the MMU at which, for instance, addresses 0 to 7 are assigned, respectively. The elements X(0) to X(3) are loaded into one vector register of the system and the elements X(4) to X(7) are loaded into another vector register of the system.
Next, a first pair of X(0) and X(4), a second pair of X(1) and X(5), a third pair of X(2) and X(6), and a fourth pair of X(3) and X(7) are successively supplied pair by pair from the two vector registers to the vector processing section of a system in which each of the pairs is subjected to different first and second operations. The results of the operations are successively stored into the storage locations of addresses 0 to 7. Specifically, the results of the first operation on the first to fourth pairs are stored into the storage locations of addresses 0, 2, 4 and 6, respectively, and those of the second operation on the first to fourth pairs are stored into the storage locations of addresses 1, 3, 5 and 7, respectively. The contents of the storage locations are again loaded into the two vector registers, and the same process is repeated. A vector consisting of elements A(0), A(4), A(2), A(6), A(1), A(5), A(3) and A(7) ultimately obtained in the storage locations of addresses 0 to 7 is a bit-reversed order vector. Therefore, the following bit reversal processing is required. Namely, the elements of the bit-reversed order vector are permutated to obtain a natural order vector having the elements A(0), A(1), A(2), A(3), A(4), A(5), A(6) and A(7) arranged in that order. First, there is formed a sequence of integer numbers [0, 1, 2, 3, 4, . . . . , N-1] (where N represents the length of the bit-reversed order vector, or the number of its vector elements). If N is 8, there will be obtained a sequence of [0, 1, 2, 3, 4, 5, 6, 7], which can be represented in binary notation as a binary sequence of [000, 001, 010, 011, 100, 101, 110, 111]. By permutating the order of bits in each three-bit string (a.sub.3 a.sub.2 a.sub.1) in the binary sequence, there is obtained a sequence of [000, 100, 010, 110, 001, 101, 011, 111] in which each three-bit string is a string (a.sub.1 a.sub.2 a.sub.3). The sequence thus obtained can be represented in decimal notation as a sequence of [0, 4, 2, 6, 1, 5, 3, 7]. Permutation vector consisting of such a sequence is stored in advance in the MMU. In a permutating process, with the elements (0, 4, 2, 6, 1, 5, 3, 7) of the permutation vector being used as addresses, the elements A(0), A(1), A(2), A(3), A(4), A(5), A(6) and A(7) in the storage locations of addresses 0, 4, 2, 6, 1, 5, 3 and 7 are loaded into a vector register in this order for transfer from this vector register into a desired area in the MMU.
Since the MMU is usually composed of a plurality of banks each permitting independent access, access to vector elements stored in different banks can be made simultaneously. Generally, the number of banks is a power of 2, resulting in frequent occurrences of bank conflict (simultaneous access requests to the same bank) in the above-mentioned permutating process. For instance, if the number of banks is four, the order of addresses designated by the permutation vector is an order of addresses 0, 4, 2, 6, 1, 5, 3 and 7 in the above-mentioned permutating process. In this case, addresses 0 and 4, addresses 2 and 6, and addresses 3 and 7 belong to the same banks, respectively, and access to the two addresses of each of the address pairs is made consecutively to avoid a bank conflict. A bank conflict brings about a substantial increase in data transfer time due to waiting for memory access.
An object of the present invention is, therefore, to provide a method free from the disadvantage mentioned above.